class Solution(object):
    def minTotalDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        m_length = [0] * m
        n_length = [0] * n
        for i in range(m):
            if i == 0:
                m_length[i] = sum(grid[i])
            else:
                m_length[i] = m_length[i - 1] + sum(grid[i])
        for j in range(n):
            if j == 0:
                n_length[j] = sum([k[j] for k in grid])
            else:
                n_length[j] = n_length[j - 1] + sum([k[j] for k in grid])
        i = 0
        m_dist = 0
        for i in range(1, m):
            m_dist += i * (m_length[i] - m_length[i - 1])
        min_dist = m_dist
        for i in range(1, m):
            m_dist = m_dist - (m_length[-1] - m_length[i - 1]) + m_length[i - 1]
            if m_dist < min_dist:
                min_dist = m_dist
        m_dist = min_dist
        n_dist = 0
        for i in range(1, n):
            n_dist += i * (n_length[i] - n_length[i - 1])
        min_dist = n_dist
        for i in range(1, n):
            n_dist = n_dist - (n_length[-1] - n_length[i - 1]) + n_length[i - 1]
            if n_dist < min_dist:
                min_dist = n_dist
        n_dist = min_dist
        return m_dist + n_dist


data = Solution()
grid = [[1,1]]
print(data.minTotalDistance(grid))
